﻿#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<utility>
#include<string>
#include<vector>

using namespace std;
namespace hash_bucket
{
	template<class T>
	struct HashBucketNode
	{
		T _data;
		HashBucketNode<T>* _pNext;
		HashBucketNode(const T& data)
			:_data(data)
			, _pNext(nullptr)
		{}
	};

	template<class K>
	struct DefHashF {
		size_t operator()(const K& key) {
			return key;
		}
	};

	template<>
	struct DefHashF<string> {
		size_t operator()(const string& key) {
			size_t r = 0;
			for (auto x : key) {
				r *= 13;
				r += x;
			}
			return r;
		}
	};

	// 为了实现简单，在哈希桶的迭代器类中需要用到hashBucket本身，
	template<class K, class T, class KeyOfValue, class HF>
	class HashBucket;

	template <class K, class T, class KeyOfValue, class Ptr, class Ref, class HF>
	struct HBIterator
	{
		typedef HashBucket<K, T, KeyOfValue,HF> HashBucket;
		typedef HashBucketNode<T>* PNode;
		typedef HBIterator<K, T, KeyOfValue, Ptr, Ref, HF> Self;

		HBIterator(PNode pNode = nullptr, HashBucket* pHt = nullptr)
			:_pNode(pNode)
			,_pHt(pHt)
		{}

		// 注意：因为哈希桶在底层是单链表结构，所以哈希桶的迭代器不需要--操作
		Self& operator++()
		{
			if (!_pNode) {
				return *this;
			}
			// 当前迭代器所指节点后还有节点时直接取其下一个节点
			if (_pNode->_pNext)
				_pNode = _pNode->_pNext;
			else
			{
				// 找下一个不空的桶，返回该桶中第一个节点
				KeyOfValue KeyFunc;
				size_t bucketNo = (_pHt->HashFunc(KeyFunc(_pNode->_data)))%_pHt->BucketCount() + 1;
				for (; bucketNo < _pHt->BucketCount(); ++bucketNo)
				{
					/*if (_pNode = _pHt->_ht[bucketNo])
						break;*/

					if (_pHt->_ht[bucketNo]) {
						_pNode = _pHt->_ht[bucketNo];
						break;
					}
				}
				if (bucketNo >= _pHt->BucketCount()) {
					_pNode = nullptr;
				}
			}
			return *this;
		}
		Self operator++(int) {
			Self RSelf = *this;
			operator++();
			return RSelf;
		}
		Ref operator*() {return _pNode->_data;}
		Ptr operator->() {
			return &(_pNode->_data);
		}
		bool operator==(const Self& it) const { 
			return (_pNode==nullptr&&it._pNode==nullptr)

				//_pNode->_data是iterator++的时候变成的nullptr，it_pNode==nullptr,是end()的情况
				||(&(_pNode->_data) == nullptr && it._pNode == nullptr)

				//如果&(_pNode->_data)！=nullptr&&it._pNode==nullptr)
				//it._pNode->_data会变成<struct at nullptr>为nullptr
				||(_pNode->_data == it._pNode->_data);
		}
		bool operator!=(const Self& it) const { return !this->operator==(it); }

		PNode _pNode;             // 当前迭代器关联的节点
		HashBucket* _pHt;         // 哈希桶--主要是为了找下一个空桶时候方便
	};

	template<class K, class T, class KeyOfValue, class HF>
	class HashBucket
	{
		template <class K, class T, class KeyOfValue, class Ptr, class Ref, class HF>
		friend struct HBIterator;
				typedef HashBucketNode<T> Node;
	public:
		typedef HBIterator<K, T, KeyOfValue, T*, T&, HF> Self;
		typedef HBIterator<K, T, KeyOfValue, const T*, const T&, HF> ConstSelf;

		HashBucket()
		{
			_ht.resize(10, nullptr);
		}

		// 哈希桶的销毁
		~HashBucket() {
			for (int i = 0; i < _ht.size(); i++) {
				Node* cur = _ht[i];
				while (cur) {
					Node* next = cur->_pNext;
					delete cur;
					cur = next;
				}
				_ht[i] = nullptr;
			}

		}

		// 插入值为data的元素，如果data存在则不插入
		pair<Self, bool> Insert(const T& data) {
			KeyOfValue KeyFun;
			K key = KeyFun(data);
			if (Node* PFind=Find(key)._pNode) {
				return make_pair(Self(PFind,this),false);
			}
			 
			HF HashFunc;
			if (_n == _ht.size()) {
				vector<Node*> NewTables(_ht.size() * 3, nullptr);

				for (int i = 0; i < _ht.size(); i++) {
					Node* cur = _ht[i];
					while (cur) {
						Node* next = cur->_pNext;
						size_t CurValue = HashFunc(KeyFun(cur->_data)) % NewTables.size();
						cur->_pNext = NewTables[CurValue];
						NewTables[CurValue] = cur;
						cur = next;
					}
					_ht[i] = nullptr;
				}
				_ht.swap(NewTables);
			}

			size_t value = HashFunc(key) % _ht.size();
			Node * NewNode = new Node(data);
			NewNode->_pNext = _ht[value];
			_ht[value] = NewNode;
			++_n;
			return make_pair(Self(NewNode, this), true);
		}

		// 在哈希桶中查找值为key的元素，存在返回true否则返回false﻿
		Self Find(const K& key) {
			HF HashFunc;
			size_t value = HashFunc(key) % _ht.size();

			Node* cur = _ht[value];
			KeyOfValue KeyFunc;
			while (cur) {
				//使用到==
				if (KeyFunc(cur->_data) == key) {
					return Self(cur,this);
				}
				cur = cur->_pNext;
			}
			return Self(nullptr, this);
		}

		// 哈希桶中删除key的元素，删除成功返回true，否则返回false
		pair<Self, bool> Erase(const Self& it) {
			if (it == nullptr || it._pNode == nullptr) {
				return make_pair(Self(nullptr, this), false);
			}

			KeyOfValue KeyFunc;
			const K key = KeyFunc(it._pNode->_data);
			HF HashFunc;
			size_t value = HashFunc(key) % this->BucketCount();
			Node* cur = _ht[value];
			Node* pre = nullptr;
			while (cur) {
				if (KeyFunc(cur->_data) == key) {
					Node* del = cur;
					if (pre) {
						pre->_pNext = cur->_pNext;
					}
					else {
						_ht[value] = cur->_pNext;
					}
					delete del;
					del = nullptr;
					--_n;
					return make_pair(Self(pre, this), true);
				}
				pre = cur;
				cur = cur->_pNext;
			}
		}

		size_t HashFunc(const K& key) const{HF HashFunc;return HashFunc(key);}
		//桶的数量
		const size_t& BucketCount() const{return _ht.size();}
		Self begin() {
			if (_n == 0) {
				return Self(nullptr, this);
			}

			Node* cur = nullptr;
			for (int i = 0; i < _ht.size() && cur == nullptr; i++) {
				cur = _ht[i];
			}
			//Node* cur = _ht[0];
			//while (!cur) {
			//	//++cur;错误（nullptr进行算数计算++是未定义的行径）
			//}
			return Self(cur, this);
		}
		Self end() {return Self(nullptr, this);}
		ConstSelf begin() const{
			if (_n == 0) {
				return Self(nullptr, this);
			}

			Node* cur = _ht;
			while (!cur) {
				++cur;
			}
			return Self(cur, this);
		}
		ConstSelf end() const{ return Self(nullptr, this); }
		//存入数据个数
		size_t size() const { return _n; }
		bool empty() const { return _n == 0; }
		//相同数的个数
		size_t Count (const K& key) const { return Find(key); }
		//类型T存在桶含有的数据个数
		size_t BucketSize (const K& key) const {
			HF HashFunc;
			size_t value = HashFunc(key) % _ht.size();
			Node* cur = _ht[value];
			size_t RNum = 0;
			while (cur) {
				++RNum;
				cur = cur->_pNext;
			}
			return RNum;
			return 0;
		}

	private:
		vector<Node*> _ht;  // 指针数组
		size_t _n = 0;			// 表中存储数据个数
	};
}